public class Test {
    /*
    题目 1 : 杨氏矩阵
     */
    //编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。
    // 该矩阵具有以下特性：
    //每行的元素从左到右升序排列。
    //每列的元素从上到下升序排列。
    //Z字形查找
    //时间复杂度为 O(m + n)
    public boolean searchMatrix2(int[][] matrix, int target) {
        //行
        int m = matrix.length;
        //列
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while(i < m && j >= 0){
            if(matrix[i][j] > target){
                j--;
            }else if(matrix[i][j] < target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }

    //搜索二维数组
    //编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
    //每行中的整数从左到右按升序排列。
    //每行的第一个整数大于前一行的最后一个整数。
    public boolean searchMatrix1(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = n - 1;
        while(i < m && j >= 0){
            if(matrix[i][j] > target){
                j--;
                m = i + 1;
            }else if(matrix[i][j] < target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }

    //官方思路：将这个二维数组，行与行首尾相接成一个升序的一维数组
    //再利用二分查找
    //时间复杂度：O(log2(m * n))
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(matrix[mid / n][mid % n] > target){
                right = mid - 1;
            }else if(matrix[mid / n][mid % n] < target){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }

    /*
    题目 2 ：递增的三元子序列
     */
    //给你一个整数数组nums ，判断这个数组中是否存在长度为 3 的递增子序列。
    //如果存在这样的三元组下标 (i, j, k)且满足 i < j < k
    // 使得nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if(n < 3){
            return false;
        }
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        // i 下标前的数字里，first 是最小的数字，而 second 是一个仅次于 first 的第二小的数字
        //如此一来，递增子序列中，找到第三个数字的可能就会变大！！
        for(int i = 1; i < n; i++){
            int num = nums[i];
            if(num > second){
                return true;
            }else if(num > first){
                second = num;
            }else{
                first = num;
            }
        }
        return false;
    }

}
